package leetcode.editor.cn;

import java.sql.Struct;

/**
 * 题目Id：74
 * 题目：搜索二维矩阵
 * 日期：2024-03-15 20:14:22
 */
//给你一个满足下述两条属性的 m x n 整数矩阵：
//
//
// 每行中的整数从左到右按非严格递增顺序排列。
// 每行的第一个整数大于前一行的最后一个整数。
//
//
// 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
//
//
//
// 示例 1：
//
//
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
//输出：true
//
//
// 示例 2：
//
//
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
//输出：false
//
//
//
//
// 提示：
//
//
// m == matrix.length
// n == matrix[i].length
// 1 <= m, n <= 100
// -10⁴ <= matrix[i][j], target <= 10⁴
//
//
// Related Topics 数组 二分查找 矩阵 👍 903 👎 0


public class SearchA2dMatrix {
    public static void main(String[] args) {
        Solution solution = new SearchA2dMatrix().new Solution();
        final boolean b = solution.searchMatrix(new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}}, 3);
        System.out.println(b);

        System.out.println("Hello world");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            final int row = binarySearchRow(matrix, target);
            if(row<0){
                return false;
            }

            return binarySearchCol(matrix,row,target);



        }

        public int binarySearchRow(int[][] matrix, int target) {
            int low=-1;
            int high=matrix.length-1;
            int mid;
            while (low<high){
                 mid = (high - low + 1) / 2 + low;
                if(matrix[mid][0]<target){
                    low=mid;
                }else if(matrix[mid][0]>target){
                    high=mid-1;
                }else {
                    return mid;
                }
            }
            return low;
        }
        public Boolean binarySearchCol(int[][] matrix, int row,int target) {
            int low=0;
            int high=matrix[0].length-1;
            int mid;
            while (low<=high){
                 mid = (high - low + 1) / 2 + low;
                if(matrix[row][mid]<target){
                    low=mid+1;
                }else if(matrix[row][mid]>target){
                    high=mid-1;
                }else {
                    return true;
                }
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
